/* MapKit, Generic functions */

/*
 * Copyright (c) 2002-2004, Jean-Sebastien Roy (js@jeannot.org)
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

static char const rcsid[] =
  "@(#) $Jeannot: mapkit_generic.c,v 1.16 2004/03/05 16:06:06 js Exp $";

#include "mapkit_generic.h"

const char *mapkit_error_msg[5] = {
  "ok",
  "fill >= max. admissible size",
  "malloc failed",
  "bad key",
  "key not found"
};

/* Static constants */

#if LONG_MAX <= 0x7fffffff
/* 32 bits longs */
#define MAPKIT_PRIMES 343

static mapkit_size_t mapkit_primes[MAPKIT_PRIMES] =
{5L, 7L, 13L, 19L, 31L, 43L, 61L, 73L, 103L, 109L, 139L, 151L,
181L, 193L, 199L, 229L, 241L, 271L, 283L, 313L, 349L, 421L, 433L,
463L, 523L, 571L, 601L, 619L, 643L, 661L, 811L, 829L, 859L, 883L,
1021L, 1063L, 1093L, 1153L, 1231L, 1291L, 1321L, 1429L, 1489L, 1609L,
1669L, 1723L, 1789L, 1873L, 1951L, 2029L, 2113L, 2143L, 2239L, 2341L,
2383L, 2551L, 2659L, 2791L, 2803L, 2971L, 3001L, 3121L, 3259L, 3391L,
3559L, 3673L, 3853L, 4021L, 4219L, 4423L, 4639L, 4801L, 5023L, 5233L,
5479L, 5743L, 5881L, 6133L, 6361L, 6661L, 6961L, 7309L, 7591L, 7951L,
8293L, 8629L, 9043L, 9463L, 9931L, 10333L, 10711L, 11173L, 11719L,
12253L, 12823L, 13399L, 14011L, 14629L, 15331L, 16069L, 16831L, 17659L,
18541L, 19429L, 20359L, 21319L, 22369L, 23371L, 24421L, 25603L, 26881L,
28183L, 29569L, 30871L, 32413L, 34033L, 35731L, 37363L, 39229L, 41179L,
43051L, 45181L, 47419L, 49789L, 52183L, 54631L, 57349L, 60169L, 63031L,
66109L, 69403L, 72871L, 76423L, 80233L, 84223L, 88339L, 92683L, 97303L,
102103L, 107101L, 112363L, 117979L, 123733L, 129919L, 136399L, 143113L,
150223L, 157669L, 165313L, 173431L, 182101L, 191143L, 200383L, 210361L,
220879L, 231841L, 243433L, 255589L, 267961L, 281251L, 295201L, 309931L,
325309L, 341461L, 358429L, 376099L, 394819L, 414433L, 435109L, 456811L,
479431L, 503383L, 528511L, 554893L, 582511L, 611551L, 642079L, 674161L,
707671L, 742993L, 780049L, 819031L, 859801L, 902599L, 947413L, 994711L,
1044289L, 1096351L, 1150873L, 1208299L, 1268623L, 1331989L, 1398559L,
1468459L, 1541821L, 1618831L, 1699741L, 1784581L, 1873771L, 1967419L,
2065729L, 2168989L, 2277001L, 2390473L, 2509963L, 2635099L, 2766793L,
2905033L, 3050263L, 3202483L, 3362329L, 3530071L, 3706489L, 3891781L,
4086289L, 4290469L, 4504963L, 4730179L, 4966531L, 5214823L, 5475523L,
5748961L, 6036271L, 6338029L, 6654649L, 6987109L, 7336423L, 7703239L,
8088331L, 8492593L, 8916913L, 9362671L, 9830803L, 10322161L, 10838119L,
11379961L, 11948791L, 12546013L, 13173031L, 13831669L, 14523193L,
15248671L, 16011031L, 16811131L, 17651659L, 18534169L, 19460659L,
20433691L, 21455281L, 22527469L, 23653813L, 24836311L, 26077591L,
27381469L, 28750261L, 30187609L, 31696939L, 33281659L, 34945681L,
36692881L, 38527303L, 40453549L, 42476143L, 44599741L, 46829149L,
49170421L, 51628693L, 54210073L, 56920441L, 59765779L, 62753881L,
65890753L, 69184879L, 72643801L, 76275961L, 80089663L, 84094039L,
88298521L, 92713099L, 97348243L, 102215539L, 107326033L, 112691731L,
118326181L, 124242331L, 130454101L, 136976053L, 143824789L, 151015939L,
158566651L, 166494901L, 174819583L, 183560551L, 192738463L, 202375339L,
212493961L, 223118629L, 234274321L, 245987983L, 258287221L, 271201321L,
284761159L, 298999201L, 313948993L, 329646313L, 346128283L, 363434053L,
381605641L, 400685893L, 420720019L, 441755893L, 463843339L, 487035169L,
511386781L, 536955961L, 563803063L, 591992419L, 621591913L, 652670593L,
685303783L, 719567743L, 755545711L, 793322989L, 832989109L, 874638211L,
918369919L, 964287913L, 1012502221L, 1063127293L, 1116283603L,
1172097763L, 1230702463L, 1292237251L, 1356848263L, 1424690611L,
1495924909L, 1570720981L, 1649256319L, 1731718699L, 1818304471L,
1909219603L, 2004680263L, 2147483647L};
#else
/* 64 bits longs */
#define MAPKIT_PRIMES 798

static mapkit_size_t mapkit_primes[MAPKIT_PRIMES] =
{5L, 7L, 13L, 19L, 31L, 43L, 61L, 73L, 103L, 109L, 139L, 151L,
181L, 193L, 199L, 229L, 241L, 271L, 283L, 313L, 349L, 421L, 433L,
463L, 523L, 571L, 601L, 619L, 643L, 661L, 811L, 829L, 859L, 883L,
1021L, 1063L, 1093L, 1153L, 1231L, 1291L, 1321L, 1429L, 1489L, 1609L,
1669L, 1723L, 1789L, 1873L, 1951L, 2029L, 2113L, 2143L, 2239L, 2341L,
2383L, 2551L, 2659L, 2791L, 2803L, 2971L, 3001L, 3121L, 3259L, 3391L,
3559L, 3673L, 3853L, 4021L, 4219L, 4423L, 4639L, 4801L, 5023L, 5233L,
5479L, 5743L, 5881L, 6133L, 6361L, 6661L, 6961L, 7309L, 7591L, 7951L,
8293L, 8629L, 9043L, 9463L, 9931L, 10333L, 10711L, 11173L, 11719L,
12253L, 12823L, 13399L, 14011L, 14629L, 15331L, 16069L, 16831L, 17659L,
18541L, 19429L, 20359L, 21319L, 22369L, 23371L, 24421L, 25603L, 26881L,
28183L, 29569L, 30871L, 32413L, 34033L, 35731L, 37363L, 39229L, 41179L,
43051L, 45181L, 47419L, 49789L, 52183L, 54631L, 57349L, 60169L, 63031L,
66109L, 69403L, 72871L, 76423L, 80233L, 84223L, 88339L, 92683L, 97303L,
102103L, 107101L, 112363L, 117979L, 123733L, 129919L, 136399L, 143113L,
150223L, 157669L, 165313L, 173431L, 182101L, 191143L, 200383L, 210361L,
220879L, 231841L, 243433L, 255589L, 267961L, 281251L, 295201L, 309931L,
325309L, 341461L, 358429L, 376099L, 394819L, 414433L, 435109L, 456811L,
479431L, 503383L, 528511L, 554893L, 582511L, 611551L, 642079L, 674161L,
707671L, 742993L, 780049L, 819031L, 859801L, 902599L, 947413L, 994711L,
1044289L, 1096351L, 1150873L, 1208299L, 1268623L, 1331989L, 1398559L,
1468459L, 1541821L, 1618831L, 1699741L, 1784581L, 1873771L, 1967419L,
2065729L, 2168989L, 2277001L, 2390473L, 2509963L, 2635099L, 2766793L,
2905033L, 3050263L, 3202483L, 3362329L, 3530071L, 3706489L, 3891781L,
4086289L, 4290469L, 4504963L, 4730179L, 4966531L, 5214823L, 5475523L,
5748961L, 6036271L, 6338029L, 6654649L, 6987109L, 7336423L, 7703239L,
8088331L, 8492593L, 8916913L, 9362671L, 9830803L, 10322161L, 10838119L,
11379961L, 11948791L, 12546013L, 13173031L, 13831669L, 14523193L,
15248671L, 16011031L, 16811131L, 17651659L, 18534169L, 19460659L,
20433691L, 21455281L, 22527469L, 23653813L, 24836311L, 26077591L,
27381469L, 28750261L, 30187609L, 31696939L, 33281659L, 34945681L,
36692881L, 38527303L, 40453549L, 42476143L, 44599741L, 46829149L,
49170421L, 51628693L, 54210073L, 56920441L, 59765779L, 62753881L,
65890753L, 69184879L, 72643801L, 76275961L, 80089663L, 84094039L,
88298521L, 92713099L, 97348243L, 102215539L, 107326033L, 112691731L,
118326181L, 124242331L, 130454101L, 136976053L, 143824789L, 151015939L,
158566651L, 166494901L, 174819583L, 183560551L, 192738463L, 202375339L,
212493961L, 223118629L, 234274321L, 245987983L, 258287221L, 271201321L,
284761159L, 298999201L, 313948993L, 329646313L, 346128283L, 363434053L,
381605641L, 400685893L, 420720019L, 441755893L, 463843339L, 487035169L,
511386781L, 536955961L, 563803063L, 591992419L, 621591913L, 652670593L,
685303783L, 719567743L, 755545711L, 793322989L, 832989109L, 874638211L,
918369919L, 964287913L, 1012502221L, 1063127293L, 1116283603L,
1172097763L, 1230702463L, 1292237251L, 1356848263L, 1424690611L,
1495924909L, 1570720981L, 1649256319L, 1731718699L, 1818304471L,
1909219603L, 2004680263L, 2104914271L, 2210159113L, 2320667053L,
2436700369L, 2558534863L, 2686461301L, 2820784321L, 2961823519L,
3109914463L, 3265409671L, 3428679931L, 3600113089L, 3780118621L,
3969124501L, 4167580723L, 4375959571L, 4594757509L, 4824495043L,
5065719649L, 5319004963L, 5584954621L, 5864201491L, 6157411219L,
6465281743L, 6788545669L, 7127972773L, 7484371333L, 7858589383L,
8251518469L, 8664094291L, 9097298143L, 9552162799L, 10029770899L,
10531258921L, 11057821561L, 11610712021L, 12191247619L, 12800809999L,
13440850483L, 14112891943L, 14818535863L, 15559462363L, 16337435383L,
17154304303L, 18012019033L, 18912619603L, 19858249549L, 20851162021L,
21893719921L, 22988405833L, 24137825713L, 25344716401L, 26611952023L,
27942548563L, 29339675203L, 30806658811L, 32346991741L, 33964340653L,
35662557061L, 37445682481L, 39317966071L, 41283863683L, 43348056571L,
45515459221L, 47791229623L, 50180790763L, 52689830191L, 55324321471L,
58090535023L, 60995061511L, 64044814111L, 67247053933L, 70609405513L,
74139875629L, 77846867719L, 81739211053L, 85826171569L, 90117479719L,
94623353611L, 99354520999L, 104322246649L, 109538358781L, 115015276639L,
120766040323L, 126804341893L, 133144558123L, 139801785943L, 146791874503L,
154131467131L, 161838040339L, 169929942253L, 178426439299L, 187347761059L,
196715147611L, 206550902629L, 216878447329L, 227722369339L, 239108487523L,
251063911393L, 263617106239L, 276797961259L, 290637858673L, 305169751459L,
320428238989L, 336449650219L, 353272132573L, 370935738499L, 389482524943L,
408956649469L, 429404481559L, 450874704883L, 473418439609L, 497089361581L,
521943829573L, 548041020721L, 575443071409L, 604215224551L, 634425985759L,
666147282601L, 699454645993L, 734427378103L, 771148746229L, 809706182809L,
850191491911L, 892701066403L, 937336119691L, 984202925611L, 1033413071611L,
1085083725139L, 1139337910231L, 1196304805513L, 1256120045179L,
1318926046771L, 1384872349033L, 1454115966343L, 1526821763179L,
1603162851163L, 1683320993701L, 1767487043281L, 1855861394839L,
1948654464571L, 2046087187561L, 2148391546201L, 2255811123229L,
2368601679049L, 2487031762351L, 2611383349123L, 2741952516463L,
2879050142233L, 3023002649209L, 3174152780683L, 3332860418863L,
3499503438721L, 3674478609619L, 3858202539553L, 4051112665363L,
4253668298569L, 4466351712343L, 4689669297121L, 4924152760951L,
5170360398871L, 5428878418111L, 5700322338679L, 5985338454673L,
6284605376983L, 6598835645251L, 6928777426579L, 7275216297553L,
7638977112073L, 8020925966743L, 8421972264949L, 8843070877009L,
9285224420533L, 9749485640683L, 10236959922619L, 10748807917999L,
11286248313631L, 11850560728873L, 12443088765229L, 13065243203029L,
13718505362413L, 14404430629621L, 15124652159923L, 15880884767119L,
16674929004691L, 17508675454561L, 18384109226773L, 19303314687661L,
20268480422041L, 21281904441859L, 22345999663861L, 23463299646301L,
24636464626651L, 25868287857613L, 27161702249623L, 28519787361073L,
29945776728871L, 31443065564923L, 33015218842561L, 34665979784323L,
36399278773369L, 38219242711423L, 40130204846401L, 42136715087683L,
44243550841573L, 46455728382823L, 48778514801713L, 51217440541681L,
53778312568273L, 56467228196209L, 59290589605441L, 62255119083403L,
65367875036911L, 68636268788083L, 72068082226771L, 75671486337751L,
79455060651391L, 83427813682459L, 87599204365963L, 91979164583389L,
96578122811629L, 101407028951749L, 106477380398581L, 111801249418381L,
117391311889171L, 123260877482989L, 129423921356869L, 135895117423759L,
142689873294391L, 149824366957723L, 157315585305553L, 165181364570713L,
173440432797391L, 182112454437103L, 191218077158161L, 200778981015229L,
210817930064869L, 221358826564963L, 232426767892591L, 244048106287189L,
256250511601291L, 269063037181111L, 282516189040069L, 296641998489379L,
311474098412341L, 327047803332493L, 343400193498883L, 360570203173129L,
378598713329569L, 397528648995091L, 417405081444811L, 438275335516903L,
460189102292461L, 483198557406979L, 507358485275689L, 532726409539063L,
559362730015711L, 587330866516411L, 616697409841309L, 647532280332391L,
679908894347161L, 713904339063823L, 749599556016823L, 787079533813429L,
826433510503831L, 867755186028253L, 911142945327949L, 956700092593771L,
1004535097222273L, 1054761852083113L, 1107499944685039L, 1162874941918513L,
1221018689014429L, 1282069623462961L, 1346173104633829L, 1413481759865509L,
1484155847858683L, 1558363640250409L, 1636281822261421L, 1718095913373613L,
1804000709041543L, 1894200744492733L, 1988910781716979L, 2088356320802581L,
2192774136837901L, 2302412843679721L, 2417533485863611L, 2538410160156331L,
2665330668163621L, 2798597201570449L, 2938527061648813L, 3085453414731223L,
3239726085467581L, 3401712389739493L, 3571798009224793L, 3750387909685933L,
3937907305169503L, 4134802670427643L, 4341542803947763L, 4558619944144753L,
4786550941350793L, 5025878488418239L, 5277172412838241L, 5541031033479973L,
5818082585151829L, 6108986714409409L, 6414436050127759L, 6735157852632241L,
7071915745260913L, 7425511532522983L, 7796787109147669L, 8186626464604573L,
8595957787833721L, 9025755677222701L, 9477043461083581L, 9950895634134841L,
10448440415839693L, 10970862436630939L, 11519405558461063L,
12095375836382221L, 12700144628200483L, 13335151859609851L,
14001909452590141L, 14702004925217923L, 15437105171477401L,
16208960430048979L, 17019408451549663L, 17870378874126133L,
18763897817830393L, 19702092708721561L, 20687197344157579L,
21721557211362139L, 22807635071930101L, 23948016825524251L,
25145417666799979L, 26402688550138993L, 27722822977645669L,
29108964126526519L, 30564412332851533L, 32092632949493869L,
33697264596968521L, 35382127826815741L, 37151234218156453L,
39008795929062781L, 40959235725511513L, 43007197511786173L,
45157557387373681L, 47415435256740379L, 49786207019575321L,
52275517370552743L, 54889293239080033L, 57633757901033443L,
60515445796082611L, 63541218085884829L, 66718278990176071L,
70054192939684843L, 73556902586668771L, 77234747716002061L,
81096485101801909L, 85151309356891693L, 89408874824728471L,
93879318565964671L, 98573284494261781L, 103501948718973733L,
108677046154922281L, 114110898462666361L, 119816443385799541L,
125807265555085729L, 132097628832838831L, 138702510274479409L,
145637635788203203L, 152919517577610211L, 160565493456489889L,
168593768129314393L, 177023456535779353L, 185874629362567699L,
195168360830694109L, 204926778872228263L, 215173117815838381L,
225931773706628389L, 237228362391959599L, 249089780511553453L,
261544269537130579L, 274621483013986711L, 288352557164685031L,
302770185022918213L, 317908694274062653L, 333804128987765479L,
350494335437151013L, 368019052209007741L, 386420004819456331L,
405741005060428693L, 426028055313449341L, 447329458079118319L,
469695930983072839L, 493180727532224659L, 517839763908833833L,
543731752104274861L, 570918339709487131L, 599464256694960871L,
629437469529708223L, 660909343006190899L, 693954810156499303L,
728652550664320351L, 765085178197535851L, 803339437107410461L,
843506408962777591L, 885681729410916439L, 929965815881462293L,
976464106675535479L, 1025287312009307773L, 1076551677609771973L,
1130379261490259239L, 1186898224564770163L, 1246243135793007493L,
1308555292582657939L, 1373983057211790409L, 1442682210072376321L,
1514816320575993133L, 1590557136604791001L, 1670084993435030329L,
1753589243106781699L, 1841268705262119643L, 1933332140525224759L,
2029998747551483719L, 2131498684929056983L, 2238073619175509449L,
2349977300134282729L, 2467476165140995279L, 2590849973398042621L,
2720392472067944623L, 2856412095671341201L, 2999232700454907349L,
3149194335477651103L, 3306654052251531673L, 3471986754864108193L,
3645586092607310851L, 3827865397237676521L, 4019258667099560083L,
4220221600454537311L, 4431232680477263053L, 4652794314501125203L,
4885434030226180201L, 5129705731737487051L, 5386191018324357391L,
5655500569240573411L, 5938275597702599353L, 6235189377587729959L,
6546948846467114779L, 6874296288790467079L, 7218011103229988773L,
7578911658391486813L, 7957857241311059629L, 8355750103376609851L,
8773537608545440321L, 9212214488972709751L};
#endif
/* Prototypes */

/* Implementation */

mapkit_size_t mapkit_nextprime(const mapkit_size_t n)
{
  long low, high, mid;

  if (n >= mapkit_primes[MAPKIT_PRIMES - 1])
    return mapkit_primes[MAPKIT_PRIMES - 1];
  
  for (low = -1, high = MAPKIT_PRIMES - 1; high - low > 1; )
  {
    mid = (high + low) >> 1;
    if (n <= mapkit_primes[mid]) high = mid;
    else low = mid;
  }

  return mapkit_primes[high];
}

/* similar to the hash function used in PERL */
mapkit_hash_t mapkit_strhash(const char *string)
{
  unsigned char c, *ustring = (unsigned char *)string;
  mapkit_hash_t hash = 5381; /* bernstein constant */

  for ( ; (c = *ustring++) ; )
    hash = hash*33 + c;

  return (hash + (hash >> 5));
}

/* similar to the hash function used in PERL */
mapkit_hash_t mapkit_memhash(const void *data, const size_t len)
{
	size_t i;
  unsigned char *ustring = (unsigned char *)data;
  mapkit_hash_t hash = 5381; /* bernstein constant */

  for (i = 0; i < len; i ++)
    hash = hash*33 + *ustring++;

  return (hash + (hash >> 5));
}
